#include "RBNode.h"
#include <iostream>
#include <sstream>

using namespace std;

RBNode * RBNode::nullNode = new RBNode(0);

RBNode::RBNode(uint myId)
{
	left = nullNode;
	right = nullNode;
	parent = nullNode;
	black = true;
	numOccurrences = 1;
	id = myId;
}

RBNode::~RBNode()
{
	if (left != nullNode)
		delete left;
	if (right != nullNode)
		delete right;
}	


void RBNode::leftRotate(RBNode * x) {
	RBNode * y = x->getRight();
	x->setRight(y->getLeft());
	if (y->getLeft() != nullNode)
		(y->getLeft())->setParent(x);
	y->setParent(x->getParent());
	if (x->getParent() == nullNode)
		this->setParent(y);
	else if (x == (x->getParent())->getLeft())
		(x->getParent())->setLeft(y);
	else
		(x->getParent())->setRight(y);			
	y->setLeft(x);
	x->setParent(y);
}


void RBNode::rightRotate(RBNode * x) {
	RBNode * y = x->getLeft();
	x->setLeft(y->getRight());
	if (y->getRight() != nullNode)
		(y->getRight())->setParent(x);
	y->setParent(x->getParent());
	if (x->getParent() == nullNode)
		this->setParent(y);
	else if (x == (x->getParent())->getLeft())
		(x->getParent())->setLeft(y);
	else
		(x->getParent())->setRight(y);			
	y->setRight(x);
	x->setParent(y);
}


//retorna se inseriu ou nao (soh incrementou numOccurrences)
void RBNode::insertNode(RBNode * z) {
	RBNode * y = nullNode;
	RBNode * x = this->getParent();
	while (x != nullNode) {
		y = x;
		if (z->getId() < x->getId()) {
			x = x->getLeft();
		}
		else if (z->getId() > x->getId()) {
			x = x->getRight();
		}
		else {
			x->incOccurrences();
			delete z;
			return;
		}
	}
	z->setParent(y);
	if (y == nullNode)
		this->setParent(z);
	else if (z->getId() < y->getId())
		y->setLeft(z);
	else
		y->setRight(z);
	
	z->setLeft(nullNode);
	z->setRight(nullNode);
	z->setBlack(false);
//	cout << "cout" << endl;
//	showTree(this->getParent());
	insertFixup(z);
}


void RBNode::insertFixup(RBNode * z) {
	RBNode * y;
	if (z == nullNode)
		cout << "Uehhhh" << endl;
	while (!(z->getParent()->isBlack())) {
		if (z->getParent() == ((z->getParent())->getParent())->getLeft()) {
			y = ((z->getParent())->getParent())->getRight();
			if (!(y->isBlack())) {
				z->getParent()->setBlack(true);
				y->setBlack(true);
				z->getParent()->getParent()->setBlack(false);
				z = z->getParent()->getParent();
			}
			else {
				if (z == z->getParent()->getRight()) {
					z = z->getParent();
					leftRotate(z);
				}
				z->getParent()->setBlack(true);
				z->getParent()->getParent()->setBlack(false);
				rightRotate(z->getParent()->getParent());
			}
		}
		else {
			y = z->getParent()->getParent()->getLeft();
			if (!y->isBlack()) {
				z->getParent()->setBlack(true);
				y->setBlack(true);
				z->getParent()->getParent()->setBlack(false);
				z = z->getParent()->getParent();
			}
			else {
				if (z == z->getParent()->getLeft()) {
					z = z->getParent();
					rightRotate(z);
				}
				z->getParent()->setBlack(true);
				z->getParent()->getParent()->setBlack(false);
				leftRotate(z->getParent()->getParent());
			}
		}
	}
	this->getParent()->setBlack(true);
}

void RBNode::showTree() {
	privateShowTree(this->getParent());
}

void RBNode::privateShowTree(RBNode * node) {
	if (node != nullNode) {
		privateShowTree(node->getLeft());
		cout << "Meu id eh: " << node->id << " e eu ocorro " << node->numOccurrences << " vezes." << endl;
		privateShowTree(node->getRight());
	}
//	else
//		cout << ".";
}

uint RBNode::setTreeString(string & treeString) {
	uint numOc = 0;
	privateSetTreeString(this->getParent(), treeString, numOc);
	return numOc;
}

void RBNode::privateSetTreeString(RBNode * node, string & treeString, uint & numOc) {
	if (node != nullNode) {
		privateSetTreeString(node->getLeft(), treeString, numOc);
		stringstream idStream;
		idStream << hex << node->getId();
		stringstream nodeOcStream;
		nodeOcStream << hex << node->getNumOcurrences();
		treeString += idStream.str() + ":" + nodeOcStream.str() + ":";
		numOc++;
		privateSetTreeString(node->getRight(), treeString, numOc);
	}
	cout << dec;
}
